package my.algorithm.sort;

import org.apache.commons.lang.ArrayUtils;

/**
 * 二分插入排序
 * @author xsw
 * @date 2018年9月27日
 */
public class BinaryInsertSort {
	public static void main(String[] args) {
		int[] list = {57,68,59,62};
		System.out.println(ArrayUtils.toString(list));
		sort(list);
		System.out.println(ArrayUtils.toString(list));
	}
	/**
	 * 二分插入排序
	 * @param list 待排序集合
	 */
	public static void sort(int[] list){
		if(list == null || list.length == 0) return ;
		/**
		 * 1. 一列原始数据，从左到右排序，左边为已排序区，右边为待排序区
		 * 2. “待排序值”与左边已排序区做比较，插入到合适的位置
		 * 3. 二分插入排序采取二分法寻找左边合适的插入位置
		 */
		for (int i = 1; i < list.length; i++) {
			int temp = list[i];
			int left = 0;
			int right = i - 1;
			int middle = 0;
			while(left <= right){
				middle = (left + right)/2;
				if(temp < list[middle]){
					right = middle-1;
				}else{
					left = middle+1;
				}
			}
			for (int j = i; j > left; j--) {
				list[j] = list[j-1];
			}
			if(left != i){
				list[left] = temp;
			}
		}
	}
}
